package com.leetcode.partition1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/7/30 9:40
 */
public class LC78子集 {

    public static List<List<Integer>> subsets(int[] nums) {
        return dfs(nums);
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3 };
        System.out.println(subsets(nums));
    }

    //dfs
    public static List<List<Integer>> dfs(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, nums, 0, new ArrayList<>());
        return result;
    }

    private static void dfs(List<List<Integer>> result, int[] nums, int index, List<Integer> subset) {
        result.add(new ArrayList<>(subset));
        if (nums.length == index) return;
        for (int i = index; i < nums.length; i++) {
            subset.add(nums[i]);
            dfs(result, nums, i + 1, subset);
            subset.remove(subset.size() - 1);
        }
    }

    public static List<List<Integer>> backtracking(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //空集加入
        result.add(new ArrayList<>());
        //每次找个数为1到num.length的子集并添加到result中
        for (int len = 1; len <= nums.length; len++) {
            backtracking(result, nums, len, 0, new ArrayList<>());
        }
        return result;
    }

    public static void backtracking(List<List<Integer>> result, int[] nums, int length, int index, List<Integer> subset) {
        if (subset.size() == length) {                      //剪枝
            List<Integer> temp = new ArrayList<>(subset);           //将个数为指定个数的子集添加到temp，避免引用传递
            result.add(temp);
            return;
        }
        //遍历数组，从index位置开始
        for (int i = index; i < nums.length; i++) {
            subset.add(nums[i]);
            backtracking(result, nums, length, i + 1, subset);
            subset.remove(subset.size() - 1);             //删除元素，进行回溯
        }
    }


    /**
     * 扩展法
     * nums = [1, 2, 3]
     * result = [[]]
     * num = 1：取出result所有list进行复制，将1依次加入复制的list，存放到temp的中转变量。result迭代完毕再将temp中的数据全部添加到result
     *          temp = [[1]]      result = [[], [1]]
     * num = 2：temp = [[2], [1, 2]]     result = [[], [1], [2], [1, 2]]
     * num = 3：temp = [[3], [1, 3], [2, 3], [1, 2, 3]]      result = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
     * @param nums
     * @return
     */
    public static List<List<Integer>> expansion(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());              //空集是一切集合的子集
        for (int num : nums) {
            //需要使用temp来中转，否则就需要在迭代result的过程中对result进行add，会引发异常或者死循环；使用temp来存放当前num添加到result中的子集
            List<List<Integer>> temp = new ArrayList<>();
            //将当前num追加所有的集合中
            for (List<Integer> res : result) {
                List<Integer> copyRes = new ArrayList<>(res);
                copyRes.add(num);               //遍历出来的都追加当前num
                temp.add(copyRes);
            }
            result.addAll(temp);
        }
        return result;
    }
}
